{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Guess Number Higher or Lower"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-search #interactive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #二分查找 #交互"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: guessNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #猜数字大小"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>猜数字游戏的规则如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每轮游戏，我都会从 <strong>1</strong> 到 <em><strong>n</strong></em> 随机选择一个数字。 请你猜选出的是哪个数字。</li>\n",
    "\t<li>如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你可以通过调用一个预先定义好的接口 <code>int guess(int num)</code> 来获取猜测结果，返回值一共有 3 种可能的情况（<code>-1</code>，<code>1</code> 或 <code>0</code>）：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>-1：我选出的数字比你猜的数字小 <code>pick < num</code></li>\n",
    "\t<li>1：我选出的数字比你猜的数字大 <code>pick > num</code></li>\n",
    "\t<li>0：我选出的数字和你猜的数字一样。恭喜！你猜对了！<code>pick == num</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>返回我选出的数字。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 10, pick = 6\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, pick = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, pick = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, pick = 2\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li><code>1 <= pick <= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [guess-number-higher-or-lower](https://leetcode.cn/problems/guess-number-higher-or-lower/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [guess-number-higher-or-lower](https://leetcode.cn/problems/guess-number-higher-or-lower/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10\\n6', '1\\n1', '2\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if num is higher than the picked number\n",
    "#          1 if num is lower than the picked number\n",
    "#          otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        i, j = 1, n\n",
    "        while(i<=j):\n",
    "            mid = (i+j)//2\n",
    "            if guess(mid) == 0:\n",
    "                return mid\n",
    "            if guess(mid) == -1:\n",
    "                j = mid-1\n",
    "            else:\n",
    "                i = mid+1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        l = 1\n",
    "        r = n\n",
    "        while(l<=n):\n",
    "            mid = (l + r) // 2\n",
    "            if(guess(mid) == 0):\n",
    "                return mid\n",
    "            elif(guess(mid) == 1):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        l = 0\n",
    "        r = n\n",
    "        while(l < r):\n",
    "            mid = (l+r)//2\n",
    "            if(guess(mid) == 1):\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        left, right = 1, n\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            res = guess(mid)\n",
    "            if res == 0:\n",
    "                return mid\n",
    "            elif res == -1:\n",
    "                right = mid - 1              \n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        if guess(1) == 0:\n",
    "            return 1\n",
    "        if guess(n) == 0:\n",
    "            return n\n",
    "        m1 = 1\n",
    "        m2 = n\n",
    "        m = int((m1 + m2) / 2)\n",
    "        while guess(m) != 0:\n",
    "            if guess(m1) == 0:\n",
    "                return m1\n",
    "            if guess(m2) == 0:\n",
    "                return m2\n",
    "            if guess(m) == 1:\n",
    "                m1 = m\n",
    "            else:\n",
    "                m2 = m\n",
    "            m = int((m1 + m2) / 2)\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        left, right = 0, n\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            ret = guess(mid)\n",
    "            if ret == 0: return mid\n",
    "            elif ret == 1: left = mid + 1\n",
    "            else: right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        left = 0\n",
    "        right = n\n",
    "        while left < right:\n",
    "            mid = left+(right-left)//2\n",
    "            if guess(mid) == 1:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        left = 1\n",
    "        right=n\n",
    "        \n",
    "        while True:\n",
    "            mid = int((left + right) / 2)\n",
    "            if guess(mid)==-1:\n",
    "                right=mid-1\n",
    "            elif guess(mid)==1:\n",
    "                left=mid+1\n",
    "            elif guess(mid)==0:\n",
    "                return mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        left, right = 0, n\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if guess(mid) == 0:\n",
    "                return mid\n",
    "            elif guess(mid) > 0:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        l, r = 1, n\n",
    "        while l <= r:\n",
    "            mid = l + (r - l)//2\n",
    "            if guess(mid) == 0:\n",
    "                return mid\n",
    "            elif guess(mid) == 1:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return mid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if num is higher than the picked number\n",
    "#          1 if num is lower than the picked number\n",
    "#          otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        left = 1\n",
    "        right = n\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + (right - left)//2\n",
    "            if guess(mid) <= 0:\n",
    "                right = mid -1\n",
    "\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if num is higher than the picked number\n",
    "#          1 if num is lower than the picked number\n",
    "#          otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        l, r = 1, n\n",
    "\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if guess(mid) == 0:\n",
    "                return mid\n",
    "            elif guess(mid) == -1:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if num is higher than the picked number\n",
    "#          1 if num is lower than the picked number\n",
    "#          otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        left=1\n",
    "        right=n\n",
    "        while left < right:\n",
    "            mid=(left + right)>>1\n",
    "            \n",
    "            if guess(mid)<=0:\n",
    "                right=mid                \n",
    "            else:\n",
    "                left=mid+1\n",
    "        \n",
    "        return left\n",
    "'''\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        left, right = 1, n\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if guess(mid) <= 0:\n",
    "                right = mid   # 答案在区间 [left, mid] 中\n",
    "            else:\n",
    "                left = mid + 1   # 答案在区间 [mid+1, right] 中\n",
    "        \n",
    "        # 此时有 left == right，区间缩为一个点，即为答案\n",
    "        return left\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if num is higher than the picked number\n",
    "#          1 if num is lower than the picked number\n",
    "#          otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        m = n // 2\n",
    "        def check(m, n):        \n",
    "            if guess(m) == 0 :\n",
    "                return m\n",
    "            elif guess(n) == 0:\n",
    "                return n\n",
    "            elif guess(m) == -1:\n",
    "                n, m = m, m//2\n",
    "                return check(m, n)\n",
    "            elif guess(m) == 1:\n",
    "                n, m = n, (n - m)//2 + m\n",
    "                return check(m, n)\n",
    "        \n",
    "        return check(m, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if num is higher than the picked number\n",
    "#          1 if num is lower than the picked number\n",
    "#          otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        start = 1\n",
    "        end = n\n",
    "        while True:\n",
    "            mid = (start + end) // 2\n",
    "            guess_result = guess(mid)\n",
    "            if guess_result == 0:\n",
    "                return mid\n",
    "            elif guess_result == -1:\n",
    "                end = mid\n",
    "            else:\n",
    "                start = mid + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if num is higher than the picked number\n",
    "#          1 if num is lower than the picked number\n",
    "#          otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        left, right = 1, n\n",
    "        \n",
    "        while left < right:\n",
    "            g = (left + right) // 2\n",
    "            res = guess(g)\n",
    "            if res == 0:\n",
    "                return g\n",
    "            elif res == 1:\n",
    "                left = g+1\n",
    "            else:\n",
    "                right = g-1\n",
    "\n",
    "        return left\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if num is higher than the picked number\n",
    "#          1 if num is lower than the picked number\n",
    "#          otherwise return 0\n",
    "# def guess(num: int) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def guessNumber(self, n: int) -> int:\n",
    "        l, r = 1, n\n",
    "        while l <= r:\n",
    "            mid = l + (r - l)//2\n",
    "            # print(mid)\n",
    "            if guess(mid) == 0:\n",
    "                return mid\n",
    "            elif guess(mid) == 1:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
